﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" >
<head>
    <title>Untitled Page</title>
    <pre>
<script>
function pathSearch()
{
    this.map;
    var map;
    this.width;
    this.pos=function(pos)
    {
        if(pos.length)
            return pos[1]*this.width+pos[0];
        else
            return [Math.floor(pos/this.width),pos%this.width+1];
    }
    var defaultFlag=['*','S','E',' '];
    this.loadStrMap=function(strmap,flag)
    {
        flag=flag||defaultFlag;
        this.map=new Array();
        map=this.map;
        this.width=strmap[0].length+2;
        for(var i=0;i<this.width;i++)this.map.push("*");
        
        for(var y=0;y<strmap.length;y++)
        {
            this.map.push("*");     
            for(var x=0;x<this.width;x++)
            {
           
                switch(strmap[y].charAt(x))
                {
                case flag[0]:
                    this.map.push("*");
                    break;
                case flag[1]:
                    this.start=[x+1,y+1];
                    this.map.push(" ");
                    break;
                case flag[2]:
                    this.end=[x+1,y+1];
                    this.map.push(" ");
                    break;
                case flag[3]:
                    this.map.push(" ");
                    break;
                }
            }
            this.map.push("*");

        }
        for(var i=0;i<this.width;i++)this.map.push("*");

    }
    this.loadArrMap=function(){
    
    }
    this.getPath=function(){
        var r=new Array();
        r.push(this.pos(this.end));
        
        if(map[r[0]]==" "||this.map[r[0]]=="*")return null;
        
        while(r[r.length-1]!=-1)
        {
            //document.write(r[r.length-1]+" ");
            //alert(this.map[54]);
            r.push(this.map[r[r.length-1]]);
        }
        r.pop();
        var me=this;
        
        r.tran=function(){
            for(var i=0;i<this.length;i++)
            {
                r[i]=me.pos(r[i]);
            }
            return this;
        }
        
        return r.reverse();        
    }

    this.bfs=function(){

        var queue=new Array();
        queue.push(this.pos(this.start));
        this.map[queue[0]]=-1;
        queue.insert=function(pos,curr)
        {

            if(map[pos]==" ")
            {
                map[pos]=curr;
                this.push(pos);
            }
        }
//alert(queue.length);
        while(queue.length)
        {            
            var curr=queue.shift();
            //document.write(curr+"\n");
            queue.insert(curr+1,curr);
            queue.insert(curr-1,curr);
            queue.insert(curr+this.width,curr);
            queue.insert(curr-this.width,curr);
            if(this.map[curr+1]!="*"||this.map[curr+this.width]!="*")
                queue.insert(curr+this.width+1,curr);
            if(this.map[curr+1]!="*"||this.map[curr-this.width]!="*")
                queue.insert(curr-this.width+1,curr);
            if(this.map[curr-1]!="*"||this.map[curr+this.width]!="*")
                queue.insert(curr+this.width-1,curr);
            if(this.map[curr-1]!="*"||this.map[curr-this.width]!="*")
                queue.insert(curr-this.width-1,curr);

        }

    }
    
    
    var viewer=[];

    this.show=function(){

        var size=10;
        var x=0,y=0;
        for(var i=0;i<this.map.length;i++)
        {
            if(!(i%this.width)){y++;x=0;}
            x++;
            viewer.push(document.createElement("img"));
            viewer[viewer.length-1].style.position="absolute";
            viewer[viewer.length-1].style.top=y*size+"px";
            viewer[viewer.length-1].style.left=x*size+"px";
            if(this.map[i]=="*")viewer[viewer.length-1].style.background="red";
            else viewer[viewer.length-1].style.background="blue";
            viewer[viewer.length-1].style.width=size;
            viewer[viewer.length-1].style.geight=size;
            document.body.appendChild(viewer[viewer.length-1]);
        }
        //document.writeln(this.pos([8,7]));
    }
    this.showPath=function(path)
    {
        if(viewer.length)
        {
            for(var i=0;i<path.length;i++)
            {
                viewer[path[i]].style.background="yellow";
            }
        }
    
    }
}
window.onload=function()
{
    var strmap=[
        "***     ",
        "*  S*   ",
        "* ***   ",
        "*  **   ",
        "* *E    ",
        "*****   "
    ]
    var map0=new pathSearch();
    map0.loadStrMap(strmap);
    map0.bfs();
    map0.show();
    map0.showPath(map0.getPath());
    alert(map0.getPath().tran().join(" "));

}
</script>
</pre>
</head>
<body>
封装版的广搜寻路算法 核心代码在bfs里
</body>
</html>
